package com.practice.niuke.new_direct_basics.class06;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 图的宽度优先遍历:
 *
 * 1， 利用队列实现
 * 2， 从源节点开始依次按照宽度进队列， 然后弹出
 * 3， 每弹出一个点， 把该节点所有没有进过队列的邻接点放入队列
 * 4， 直到队列变空
 */
public class Code01_BFS {

	/**
	 * 从node出发，进行宽度优先遍历
	 *
	 * @param node 开始遍历的源节点
	 */
	public static void bfs(Node node) {
		if (node == null) {
			return;
		}
		// 1. 准备一个队列
		Queue<Node> queue = new LinkedList<>();
		// 2. 使用一个set结构做记录，避免一个节点重复进入队列
		HashSet<Node> set = new HashSet<>();
		// 3. 将开始遍历的源节点放入到队列中，只要一个节点进入队列，那么它也一定要到Set中进行注册（放入Set中）
		queue.add(node);
		set.add(node);
		// 4. 当队列不为空时
		while (!queue.isEmpty()) {
			// 4.1 从队列中弹出一个节点，并打印该节点
			Node cur = queue.poll();
			System.out.println(cur.value);
			// 4.2 将当前弹出的节点的孩子节点依次放入队列中（没有入过队列就入队列，进入过队列则不用再进）
			for (Node next : cur.nexts) {
				// 之前没有进过队列
				if (!set.contains(next)) {
					set.add(next);
					queue.add(next);
				}
			}
		}
	}

}
